package com.zfcer.chapter02;

/**
 * @Classname ReverseList
 * @Description 反转链表
 * @Created by zfcer
 * @Date 2022/4/16 17:32
 */
public class ReverseList {
    /**
     * 反转链表
     *  1->2->3->4
     *  4->3->2->1
     */

    public static ListNode reverse(ListNode head){
        /**
         * 1. dummy 头插法
         * 2. 原地反转链表
         * 3. 栈辅助
         * 4. 数组辅助
         * 5. 两个队列实现栈【栈辅助】
         * 6. 递归实现
         */
        if(head == null) return null;
        ListNode p = reverse(head.next);
        if(p != null) {
            p.next = head;
            head.next = null;
        }else{
            newHead = head;
        }
        return head;
    }

    private static ListNode newHead;

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        reverse(head);

        ListNode p = newHead;
        while(p != null){
            System.out.println(p.val);
            p = p.next;
        }
    }
}
